//给你一个整数数组 nums 和整数 k ，返回最大和 sum ，满足存在 i < j 使得 nums[i] + nums[j] = sum 且 sum < 
//k 。如果没有满足此等式的 i,j 存在，则返回 -1 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [34,23,1,24,75,33,54,8], k = 60
//输出：58
//解释：
//34 和 24 相加得到 58，58 小于 60，满足题意。
// 
//
// 示例 2： 
//
// 
//输入：nums = [10,20,30], k = 15
//输出：-1
//解释：
//我们无法找到和小于 15 的两个元素。 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 100 
// 1 <= nums[i] <= 1000 
// 1 <= k <= 2000 
// 
// Related Topics 数组 双指针 二分查找 排序 👍 67 👎 0

package leetcode.editor.cn;

import java.util.Arrays;

public class _1099_TwoSumLessThanK {
    public static void main(String[] args) {
        Solution solution = new _1099_TwoSumLessThanK().new Solution();
        int[] nums = {254, 914, 110, 900, 147, 441, 209, 122, 571, 942, 136, 350, 160, 127, 178, 839, 201, 386, 462, 45, 735, 467, 153, 415, 875, 282, 204, 534, 639, 994, 284, 320, 865, 468, 1, 838, 275, 370, 295, 574, 309, 268, 415, 385, 786, 62, 359, 78, 854, 944};
        int k = 200;
//        int[] nums = {34, 23, 1, 24, 75, 33, 54, 8};
//        int k = 60;
        System.out.println(solution.twoSumLessThanK(nums, k));
    }

    class Solution {
        public int twoSumLessThanK(int[] nums, int k) {
            Arrays.sort(nums);
            int left = 0;
            int right = nums.length - 1;
            int sum = -1;
            while (left <= right) {
                int l = nums[left];
                int r = nums[right];
                if (l + r >= k) {
                    right--;
                    continue;
                } else {
                    sum = Math.max(sum, l + r);
                    left++;
                    continue;
                }
            }
            return sum;
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution1 {
        public int twoSumLessThanK(int[] nums, int k) {
            Arrays.sort(nums);
            int sum = -1;
            int min = Integer.MAX_VALUE;
            for (int i = 0; i < nums.length; i++) {
                for (int j = i + 1; j < nums.length; j++) {
                    int tmp = nums[i] + nums[j];
                    if (tmp >= k) continue;
                    int cha = Math.abs(tmp - k);
                    if (cha < min) {
                        min = cha;
                        sum = tmp;
                    }
                }
            }
            return sum;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}